package top.dprkshow.practice.graph;


import edu.princeton.cs.algs4.Queue;

/**
 * @author Kent HAN
 * @date 2021/9/12
 */
public class BfsPaths {
    boolean[] visited;
    int[] edgeTo, distTo;
    public BfsPaths(MatrixGraph graph, int source) {
        visited = new boolean[graph.getTotalVertices()];
        edgeTo = new int[graph.getTotalVertices()];
        distTo = new int[graph.getTotalVertices()];
        for (int i = 0; i < graph.getTotalVertices(); i++) {
            distTo[i] = Integer.MAX_VALUE;
        }
        validateVertex(source);
        bfs(graph, source);
    }

    public BfsPaths(Digraph graph, int source) {
        visited = new boolean[graph.getTotalVertices()];
        edgeTo = new int[graph.getTotalVertices()];
        distTo = new int[graph.getTotalVertices()];
        for (int i = 0; i < graph.getTotalVertices(); i++) {
            distTo[i] = Integer.MAX_VALUE;
        }
        validateVertex(source);
        bfsDigraph(graph, source);
    }

    private void bfsDigraph(Digraph graph, int source) {
        distTo[source] = 0;
        visited[source] = true;
        Queue<Integer> queue = new Queue<>();
        queue.enqueue(source);
        while (!queue.isEmpty()) {
            Integer sourceVertex = queue.dequeue();
            for (Integer adjVertex : graph.adj(sourceVertex)) {
                if (!visited[adjVertex]) {
                    visited[adjVertex] = true;
                    edgeTo[adjVertex] = sourceVertex;
                    distTo[adjVertex] = distTo[sourceVertex] + 1;
                    queue.enqueue(adjVertex);
                }
            }
        }
    }

    private void bfs(MatrixGraph graph, int source) {
        distTo[source] = 0;
        visited[source] = true;
        Queue<Integer> queue = new Queue<>();
        queue.enqueue(source);
        while (!queue.isEmpty()) {
            Integer sourceVertex = queue.dequeue();
            for (Integer adjVertex : graph.adj(sourceVertex)) {
                if (!visited[adjVertex]) {
                    visited[adjVertex] = true;
                    edgeTo[adjVertex] = sourceVertex;
                    distTo[adjVertex] = distTo[sourceVertex] + 1;
                    queue.enqueue(adjVertex);
                }
            }
        }
    }

    private void validateVertex(int vertex) {
        if (vertex < 0 || vertex >= visited.length) {
            throw new IllegalArgumentException("vertex " + vertex + " is not between 0 and " + (vertex - 1));
        }
    }
}
